//https://www.nowcoder.com/practice/57aa0bab91884a10b5136ca2c087f8ff?tpId=13&tqId=2305268&ru=%2Fpractice%2F6e196c44c7004d15b1610b9afca8bd88&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
//问题：二叉搜索树，第k个节点；
//思路1：中序遍历实现；
//思路2:递归实现；
//重要思路：！！！

#include <stack>
#include <vector>
#include <iostream>

using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    int KthNode(TreeNode* proot, int k) {
        // write code here
        if (proot == nullptr) return -1;
        if (k < 1) return -1;

        stack<TreeNode*> node_stack;
        int target_val = -1;
        TreeNode* cur = proot;
        int num = 0;

        while(!node_stack.empty() || cur != nullptr) {
           if(cur != nullptr) {
                node_stack.push(cur);
                cur=cur->left;
           }else{
             cur = node_stack.top();
             node_stack.pop();
             if (k-1 == num) {
                target_val = cur->val;
                break;
             }
             ++num;
             cur = cur->right;
           }

        }
        return target_val;
    }
};